package com.dfrz.ch06;

import java.util.Arrays;

/**
 * 作者：wangmaokang
 * 日期: 2021/4/13 15:31
 * 描述:
 */
public class QuickSortTest {
    public static void main(String[] args) {
        int[] ints={1111,2222,555,33,777,68,67,99,56,111};
        QuickSort(ints,0,ints.length-1);
        for (int anInt : ints) {
            System.out.print(anInt+",");
        }
    }

    public static void QuickSort(int[] ints,int left,int right){

        if (left<right) {  //左边必须小于右边

            int base = ints[left];

            int i = left;
            int j = right;

            while (i != j) {
                //从右往左找，找到一个比基准数字小的值
                while (ints[j] >= base && i < j) {
                    j--;
                }
                //从左往右找，找到一个比基准大的值
                while (ints[i] <= base && i < j) {
                    i++;
                }

                if (i < j) { //确保左边的位置比右边小，实现对调
                    int tmp = ints[i];
                    ints[i] = ints[j];
                    ints[j] = tmp;
                }
            }

          //当两个值相遇的时候，将基准位置和相遇位置对调
            ints[left] = ints[i];
            ints[i] = base;

            //从相遇位置划分左右两个数组继续排序
            QuickSort(ints, left, j - 1);
            QuickSort(ints, i + 1, right);

        }
    }
}
